package cg.studio.practise;

import org.junit.Test;

public class Binaries
{
  @Test
  public void testNextBiggerSparseNum()
  {
    final int total = 128;
    int correctCount = 0;
    for( int i=0; i<total; ++i )
    {
      if( nextBiggerSparseNum_deduce(i) != nextBiggerSparseNum_try(i) )
        System.out.println( "" + i + ": " + toBinaryString(i) + " ==> " + toBinaryString( nextBiggerSparseNum_deduce(i) ) 
                            + ", " + toBinaryString( nextBiggerSparseNum_try(i) ) );
      else
        correctCount++;
    }
    System.out.println( "Total " + total + ". Correct Count: " + correctCount ); 

  }
  
  
  public static String toBinaryString( int num )
  {
    return Integer.toBinaryString( num );
  }
  
  /**
   * Sparse number is an integer if there are no adjacent 1 in it's binary representation. 
   * Like: 5 -> 101 (no adjacent 1) 
   * 9 -> 1001 (no adjacent 1) 
   * while 6-> 110 is not sparse number. 
   * 
   * if num is Sparse number, so num & ( num << 1 ) should zero
   * 
   */
  public static boolean isSparseNumber( int num )
  {
    return ( num & ( num << 1 ) ) == 0;
  }
  
  /**
   * you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.
   */
  public static int nextBiggerSparseNum_try( int num )
  {
    //it can implemented by increase one and then check if it is sparse num
    while( true )
    {
      if( isSparseNumber( ++num ) )
        return num;
    }
  }
  
  /**
   * instead of by increase and test to find the next bigger Sparse Number,
   * try to get the number by deduce and calculation.
   * 
   * if the bit of the number is ba, and number of 1 is b1, number of zero is b0, then
   * the most largest sparse number of fix bit number is
   *   - if ba is odd, then, have (ba+1)/2 of '1' and (ba-1)/2 of '0'; for example 10101
   *   - if ba is even, then have ba/2 of '1' and '0'; for example: 1010
   * for any sparse number, must: b1-b0<=1, namely b1<(ba+1)/2 ( if the number of '1' large than half, 
   * it must have adjacent '1' )
   * 
   * so, for a give number num, 
   *  - if num >= max( sparse num ) , then, don't have any sparse number bigger and with the same bits, 
   *    so, next bigger sparse number is 10...0 with (bn+1) bits totally
   *  - else, this number must have adjacent 0 ( if don't have adjacent 0, then, the minimal value should be '1010',
   *    this number >= max( sparse num ) ), and don't have adjacent 1 before adjacent 0 ( or this number >= max( sparse num ) )
   *    so, for this case, this problem converted to find bigger sparse number of number start with adjacent 0
   *    
   * for example:
   *   biggerSparse(100111) = 100000 + biggerSparse(111) = 101000
   *   biggerSparse(10001) = 10000 + biggerSparse(1) = 10010
0 ==> 1
1 ==> 10
10 ==> 100
11 ==> 100
100 ==> 101
101 ==> 1000
110 ==> 1000
111 ==> 1000
1000 ==> 1001
1001 ==> 1010
1010 ==> 10000
1011 ==> 10000
1100 ==> 10000
1101 ==> 10000
1110 ==> 10000
1111 ==> 10000
10000 ==> 10001
10001 ==> 10010
10010 ==> 10100
10011 ==> 10100
10100 ==> 10101
10101 ==> 100000
10110 ==> 100000
10111 ==> 100000
11000 ==> 100000
11001 ==> 100000
11010 ==> 100000
11011 ==> 100000
11100 ==> 100000
11101 ==> 100000
11110 ==> 100000
11111 ==> 100000
   */
  public static int nextBiggerSparseNum_deduce( int num )
  {
    if( num == 0 )
      return 1;
    int ba = bitNumber( num );
    int maxSparseNum = maxSparseNumber( ba );
    if( num >= maxSparseNum )
      return power2( ba+1 );
    int adjacent0 = findAdjacent( num, true );
    int adjacent0Power = power2( adjacent0 );
    int recusiveNum = num & ( adjacent0Power - 1 );
    return num-recusiveNum + nextBiggerSparseNum_deduce( recusiveNum );
  }
  
  public static int bitNumber( int num )
  {
    int power2 = 1;
    for( int i=1; ; ++i )
    {
      if( num == power2 )
        return i;
      if( num < power2 )
        return i-1;
      power2 <<= 1;
    }
  }
  
  public static int maxSparseNumber( int bitNum )
  {
    int value = 1;
    boolean increase = false;
    for( int i=1; i<bitNum; ++i )
    {
      value <<= 1;
      if( increase )
        value++;
      increase = !increase;
    }
    return value;
  }
  
  public static int power2( int bitNum )
  {
    int value = 1;
    for( int i=1; i<bitNum; ++i )
    {
      value <<= 1;
    }
    return value;
  }
  
  /**
   * return the index of first adjacent 0/1
   * for example: 1001001, return 5
   * @param number
   * @param zero
   * @return
   */
  public static int findAdjacent( int number, boolean zero )
  {
    int bitNum = bitNumber( number );
    int power2 = power2( bitNum );
    boolean preFit = false;
    for( int i=bitNum; i>=0; --i )
    {
      int result = power2 & number;
      boolean curFit = ( zero ? ( result == 0 ) : ( result != 0 ) );
      if( curFit && preFit )
        return i;
      preFit = curFit;
      power2 >>= 1;
    }
    return 0;   //invalid actually
  }

}
